package Algorithm.greedyAlgorithm;

import java.util.Arrays;

/**
 * 455. 分发饼干 https://leetcode.cn/problems/assign-cookies/
 * 题目简述：你是家长 有一组饼干s[]，s[i]为饼干的尺寸，有一组孩子g[]，g[i]为孩子能满足的最小饼干尺寸，返回可满足的最多孩子数
 */
public class FindContentChildren {

    /**
     * 思路：先排序，然后双指针倒序查找，大饼干优先满足胃口较大的孩子（局部最优）
     */
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int gp=g.length-1, sp=s.length-1, n=0;
        while(gp >= 0 && sp >=0) {
            //找到当前最大饼干分配给能满足的当前胃口最大的孩子
            if(s[sp] >= g[gp]) {
                n++;
                sp--;
                gp--;
            } else {
                gp--;
            }
        }
        return n;
    }
}
